package 五排序;

/**
 * @Author XuZhuHong
 * @CreateTime 2021/9/17 14:45
 * 希尔排序
 * 1为交换法
 * 2为插入法（快一些）
 */
public class ShellSort {
    public static void main(String[] args) {
        int i = 10;
        int[] array = new int[i];
        //生成随机排序
        for (int k = 0; k < 10; k++) {

            for (int j = 0; j < i; j++) {
                array[j] = (int) (Math.random() * i * 10);
            }

            //原本数组：
            System.out.printf("第%d \t次数组=》   ", (k + 1));
            for (int i1 : array) {
                System.out.print(i1 + " \t");
            }

            //开始排序
            //交换法
//            shellSort(array);
            //移动法
            shellSort2(array);
            //输出
            System.out.printf("，排序后为=》   ", (k + 1));
            for (int i1 : array) {
                System.out.print(i1 + " \t");
            }
            System.out.println();
        }

    }

    private static void shellSort2(int[] array) {
        //判断第一次需要分成多少组

        //表示定下来需要把这个数组分成几组  第一次是length/2  第二次是第一次的基础上/2 以此类推  直到 结果等于0
        for (int gap = array.length / 2; gap > 0; gap /= 2) {
            //表示从哪个位置开始计算他交换的位置
            for (int i = gap; i < array.length; i++) {
                int insertIndex = i;
                int insetValue = array[i];

                //如果比他小就进行交换
                while (insertIndex - gap >= 0 && insetValue < array[insertIndex - gap]) {
                    array[insertIndex] = array[insertIndex - gap];
                    insertIndex -= gap;
                }

                array[insertIndex] = insetValue;



            }
        }


    }

    private static void shellSort(int[] array) {
        //判断第一次需要分成多少组

        //表示定下来需要把这个数组分成几组  第一次是length/2  第二次是第一次的基础上/2 以此类推  直到 结果等于0
        for (int i = array.length / 2; i > 0; i /= 2) {
            //表示从哪个位置开始计算他交换的位置
            for (int j = i; j < array.length; j++) {
                //开始判断 并且进行交换
                for (int k = j - i; k >= 0; k -= i) {
                    //进行交换
                    if (array[k] > array[k + i]) {
                        array[k + i] = array[k + i] + array[k];
                        array[k] = array[k + i] - array[k];
                        array[k + i] = array[k + i] - array[k];
                    }
                }
            }
        }


    }
}
